\chapter{Introdução}
Alguns dos exercícios deste capítulo pedem que seja desenhado a região factível de um PL sendo importante o leitor fazer alguns destes desenhos. Em \url{http://www.zweigmedia.com/RealWorld/LPGrapher/lpg.html} encontra-se disponível um aplicativo que produz uma figura com a região viável.

\begin{description}
	\item[1.24] Considere o seguinte problema:
	\[
		\begin{array}{ll}
			\mbox{Max} & z = 2x_1 + 5x_2 \\
			\mbox{st} & x_1 + 2x_2 \leq 16 \\
			& 2x_1 + x_2 \leq 12 \\
			& x_1 , x_2 \geq 0
		\end{array}
	\]
	\begin{enumerate}
		\item Desenhe a região factível.
		
		\begin{solution}
		A região factível é ilustrada na Figura~\ref{fig:Ex1.24}.
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=0.5,domain=-0.2:7.2]
				\fill[color=gray!20] (0,0) -- (0,8) -- (8/3,20/3) -- (6,0) -- (0,0);
				
				\draw[very thin,color=gray] (-0.1,-2.1) grid (6.9,8.9);
				
				\draw[->] (-0.2,0) -- (7.2,0) node[right] {$x_1$};
				\draw[->] (0,-2.2) -- (0,9.2) node[above] {$x_2$};
				
				\clip (-0.2,-2.8) rectangle (15.2,9.2);
				
				\draw[color=blue] plot (\x,0.5*16-0.5*\x) node[right] {$x_1 + 2x_2 \leq 16$};
				\draw[color=red] plot (\x,12-2*\x) node[right] {$2x_1 + x_2 \leq 12$};
				\foreach \nivel in {0,4,8,12,16,20}{
					\draw[color=black] plot (\x,0.5*\nivel - 0.5*2*\x) node[right] {$z = \nivel$};
				}
			\end{tikzpicture}
			\caption{Região factível do exercício 1.24.} \label{fig:Ex1.24}
		\end{figure}
		\end{solution}
		
		\item Identifique a região onde as variáveis de folga $s_1$ e $s_2$ são iguais a zero.
		
		\begin{solution}
		No ponto $(\frac{8}{3},\frac{20}{3})$.
		\end{solution}
		
		\item Resolva o problema geometricamente.
		
		\begin{solution}
		O ponto ótimo é $(\frac{8}{3},\frac{20}{3})$.
		\end{solution}
		
		\item Interprete a factibilidade.
		
		\begin{solution}
			
		\end{solution}
	\end{enumerate}
	
	\item [1.25] Desenhe a região factível para o conjunto $\{ \mathbf{x}: \mathbf{A}\mathbf{x} \leq \mathbf{b} \}$.
	\begin{enumerate}
		\item $\mathbf{A} = \left[ \begin{array}{cc}
		1 & 1 \\
		2 & -1 \\
		0 & 1
		\end{array} \right]$ e $\mathbf{b} = \left[ \begin{array}{c}
		6 \\
		6 \\
		2
		\end{array} \right]$
		
		\begin{solution}
		A região em cinza da Figura~\ref{fig:Ex1.25A}
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=0.5,domain=-0.2:7.2]
				\fill[color=gray!20] (-2.2,-2.2) -- (1.9,-2.2) -- (4,2) -- (-2.2,2);
				
				\draw[very thin,color=gray] (-0.1,-2.1) grid (6.9,8.9);
				
				\draw[->] (-0.2,0) -- (7.2,0) node[right] {$x_1$};
				\draw[->] (0,-2.2) -- (0,9.2) node[above] {$x_2$};
				
				\clip (-0.2,-2.2) rectangle (15.2,9.2);
				
				\draw[color=blue] plot (\x,6-\x) node[right] {$x_1 + x_2 \leq 6$};
				\draw[color=cyan] plot (\x,-6+2*\x) node[right] {$2x_1 - x_2 \leq 6$};
				\draw[color=green] plot (\x,2) node[right] {$0x_1 + x_2 \leq 2$};
			\end{tikzpicture}
			\caption{Região factível do exercício 1.25.} \label{fig:Ex1.25A}
		\end{figure}
		\end{solution}
		
		\item $\mathbf{A} = \left[ \begin{array}{cc}
		-1 & 0 \\
		0 & -1 \\
		2 & 3 \\
		1 & -1
		\end{array} \right]$ e $\mathbf{b} = \left[ \begin{array}{c}
		0 \\
		0 \\
		12 \\
		5
		\end{array} \right]$
		
		\begin{solution}
		A região em cinza da Figura~\ref{fig:Ex2.25B}.
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=0.5,domain=-0.2:7.2]
				\fill[color=gray!20] (0,0) -- (0,4) -- (5,0.7) -- (5.4,0.33) -- (5,0) -- (0,0);
					
					\draw[very thin,color=gray] (-0.1,-2.1) grid (6.9,4.9);
					
					\draw[->] (-0.2,0) -- (7.2,0) node[right] {$x_1$};
					\draw[->] (0,-2.2) -- (0,5.2) node[above] {$x_2$};
					
					\clip (-0.2,-2.2) rectangle (15.2,5.2);
					
				\draw[color=blue] plot (\x,0.33*12 - 0.33*2*\x) node[right] {$2x_1 + 3x_2 \leq 12$};
				\draw[color=cyan] plot (\x,-5+\x) node[right] {$x_1 - x_2 \leq 5$};
			\end{tikzpicture}
			\caption{Região factível do exercício 2.25.} \label{fig:Ex2.25B}
		\end{figure}
		\end{solution}
		
		\item $\mathbf{A} = \left[ \begin{array}{cc}
		1 & 1 \\
		-1 & -2 \\
		-1 & 0
		\end{array} \right]$ e $\mathbf{b} = \left[ \begin{array}{c}
		4 \\
		-12 \\
		0
		\end{array} \right]$
		
		\begin{solution}
		A região em cinza da Figura~\ref{fig:Ex2.25C}.
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=0.5,domain=-0.2:6.2]
				
				\draw[very thin,color=gray] (-0.1,-2.1) grid (5.9,5.9);
				
				\draw[->] (-0.2,0) -- (6.2,0) node[right] {$x_1$};
				\draw[->] (0,-2.2) -- (0,6.2) node[above] {$x_2$};
				
				\clip (-0.2,-3.2) rectangle (15.2,6.2);
				
				\draw[color=blue] plot (\x,4 - \x) node[right] {$x_1 + x_2 \leq 4$};
				\draw[color=cyan] plot (\x,0.5*12 - 0.5*\x) node[right] {$-x_1 -2x_2 \leq -12$};
			\end{tikzpicture}
			\caption{Região factível do exercício 2.25.} \label{fig:Ex2.25C}
		\end{figure}
		\end{solution}
	\end{enumerate}
	
	\item [1.26] Considere o seguinte problema:
	\[
		\begin{array}{ll}
		\mbox{Max} & z = 2x_1 + 3x_2 \\
		\mbox{st} & x_1 + 2x_2 \leq 2 \\
		& 4x_1 + 6x_2 \leq 9 \\
		& x_1 , x_2 \geq 0
		\end{array}
	\]
	\begin{enumerate}
		\item Desenhe a região factível.
		
		\begin{solution}
		A região em cinza da Figura~\ref{fig:Ex1.26}.
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=1,domain=-0.2:3]
				\fill[color=gray!20] (0,0) -- (2,0) -- (1.5,0.5) -- (0,1.55);
				
				\draw[very thin,color=gray] (-0.1,-1.1) grid (3.9,2.9);
				
				\draw[->] (-0.2,0) -- (4.2,0) node[right] {$x_1$};
				\draw[->] (0,-0.2) -- (0,3.2) node[above] {$x_2$};
				
				\clip (-0.2,-1.2) rectangle (6.2,3.2);
				
				\draw[color=blue] plot (\x,2-\x) node[right] {$x_1 + x_2 \leq 2$};
				\draw[color=cyan] plot (\x,0.17*9 -0.17*4*\x) node[right] {$4x_1 + 6x_2 \leq 9$};
				
				\foreach \nivel in {0,4,8}{
					\draw[color=black] plot (\x,0.33*\nivel - 0.33*2*\x) node[right] {$z = \nivel$};
				}
			\end{tikzpicture}
			\caption{Região factível do exercício 1.26.} \label{fig:Ex1.26}
		\end{figure}
		\end{solution}
		
		\item Encontre dois pontos extremos ótimos.
		
		\begin{solution}
		O primeiro ponto extremo ótimo é $(\frac{3}{2},\frac{1}{2})$ e o outro é $(0, \frac{3}{2})$.
		\end{solution}
		
		\item Encontre uma classe infinita de soluções ótimas.
		
		\begin{solution}
		A classe infinita é representada por $(\frac{3}{2},\frac{1}{2}) \alpha + (0, \frac{3}{2})[1 - \alpha]$ para $0 \leq \alpha \leq 1$.
		\end{solution}
	\end{enumerate}
	
	\item [1.27] Considere o seguinte problema:
	\[
		\begin{array}{ll}
		\mbox{Max} & z = 3x_1 + x_2 \\
		\mbox{st} & -x_1 + 2x_2 \leq 6 \\
		& x_2 \leq 4
		\end{array}
	\]
	
	\begin{enumerate}
		\item Desenhe a região factível.
		
		\begin{solution}
		Região em cinza da Figura~\ref{fig:Ex1.27}.
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=1,domain=-1.2:4.2]
				\fill[color=gray!20] (-1.1,-1.1) -- (-1.1,2.45) -- (2,4) -- (3.9,4) -- (3.9,-1.1);
				
				\draw[very thin,color=gray] (-1.1,-1.1) grid (3.9,4.9);
				
				\draw[->] (-1.2,0) -- (4.2,0) node[right] {$x_1$};
				\draw[->] (0,-0.2) -- (0,5.2) node[above] {$x_2$};
				
				\clip (-1.2,-1.2) rectangle (8.2,5.2);
				
				\draw[color=blue] plot (\x,0.5*6+0.5*\x) node[below right] {$-x_1 +2x_2 \leq 6$};
				\draw[color=cyan] plot (\x,4) node[right] {$x_2 \leq 4$};
				
				\foreach \nivel in {0,4,8,12}{
					\draw[color=black] plot (\x,\nivel - 3*\x) node[right] {$z = \nivel$};
					}
			\end{tikzpicture}
			\caption{Região factível do exercício 1.27.} \label{fig:Ex1.27}
		\end{figure}
		\end{solution}
		
		\item Verifique que o problema tem solução ótima ilimitada.
		
		\begin{solution}
		Acompanhar as curvas de níveis de $z$.
		\end{solution}
	\end{enumerate}
	
	\item [1.28] Considere o seguinte problema:
	\[
		\begin{array}{ll}
		\mbox{Max} & z = -x_1 - x_2 + 2x_3 + x_4 \\
		\mbox{st} & x_1 + x_2 + x_3 + x_4 \geq 6 \\
		& x_1 - x_2 -2x_3 + x_4 \leq 4 \\
		& x_1, x_2, x_3, x_4 \geq 0
		\end{array}
	\]
	\begin{enumerate}
		\item Introduza variáveis de folga e desenhe o espaço de exigência.
		
		\begin{solution}
		Colocando o problema na forma padrão de minimização.
		\[
			\begin{array}{ll}
			\mbox{Min} & z = -x_1 - x_2 + 2x_3 + x_4 \\
			\mbox{st} & x_1 + x_2 + x_3 + x_4 - s_5 = 6 \\
			& x_1 - x_2 -2x_3 + x_4 + s_6 = 4 \\
			& x_1, x_2, x_3, x_4 \geq 0
			\end{array}
		\]
		
		O espaço de exigência é apresentado em cinza na Figura~\ref{fig:Ex1.28} (fora de escala).
		\begin{figure}[!h]
			\centering
			\begin{tikzpicture}[scale=1]
				\fill[color = gray!20] (0,0) circle (2);
				\draw[->] (0,0) -- (1,1) node[above right] {$a_1$};
				\draw[->] (0,0) -- (1,-1) node[right] {$a_2$};
				\draw[->] (0,0) -- (1/2,-2/2) node[left] {$a_3$};
				\draw[->] (0,0) -- (1,1) node[below right] {$a_4$};
				\draw[->] (0,0) -- (-1,0) node[left] {$a_5$};
				\draw[->] (0,0) -- (0,1) node[right] {$a_3$};
				\draw[->] (0,0) -- (6/7,4/7) node[right] {$b$};
			\end{tikzpicture}
			\caption{Região factível do exercício 1.28.} \label{fig:Ex1.28}
		\end{figure}
		\end{solution}
		
		\item Interprete a factibilidade pelo espaço de exigência.
		
		\begin{solution}
		O problema admite solução factível.
		\end{solution}
		
		\item Uma solução ótima pode ser obtida tendo no máximo duas variáveis $\geq 0$ e as demais $=0$. Encontre uma solução ótima.
		
		\begin{solution}
		A solução $(0,6,0,0,0,10)$ é ótima.
		\end{solution}
	\end{enumerate}
	
	\item [1.29] Considere o problema: Minimizar $\mathbf{c}^T \mathbf{x}$ sujeito a $\mathbf{A}\mathbf{x} \geq \mathbf{b}$, $\mathbf{x} \geq 0$. Suponha que uma componente do vetor $\mathbf{b}$, digamos $b_i$, é incrementado em uma unidade.
	\begin{enumerate}
		\item O que acontece com a região factível?
		
		\begin{solution}
		A região factível é modificada.
		\end{solution}
		
		\item O que acontece com o valor ótimo?
		
		\begin{solution}
		Se a folga correspondente a $i$-ésima restrição era zero então o valor ótimo é alterado, caso contrário nada ocorre.
		\end{solution}
	\end{enumerate}
	
	\item [1.32] Considere o problema:  Minimizar $\mathbf{c}^T \mathbf{x}$ sujeito a $\mathbf{A}\mathbf{x} \geq \mathbf{b}$, $\mathbf{x} \geq 0$. Suponha que uma nova restrição, $m+1$, é adicionada ao problema.
	\begin{enumerate}
		\item O que acontece com a região factível?
		
		\begin{solution}
		A região factível pode ou não ser modificada.
		\end{solution}
		
		\item O que acontece com o valor ótimo?
		
		\begin{solution}
		Caso a região factível não seja modificada o valor ótimo é mantido. Já se a região factível for alterada temos que o valor ótimo é modificado se a solução ótima tornar-se infactível ou é mantido se a solução ótima continuar factível.
		\end{solution}
	\end{enumerate}
	
	\item [1.33] Considere o problema:  Minimizar $\mathbf{c}^T \mathbf{x}$ sujeito a $\mathbf{A}\mathbf{x} \geq \mathbf{b}$, $\mathbf{x} \geq 0$. Suponha que uma nova variável, $n+1$, é adicionada ao problema.
	\begin{enumerate}
	\item O que acontece com a região factível?
	
	\begin{solution}
	A região factível aumenta.
	\end{solution}
	
	\item O que acontece com o valor ótimo?
	
	\begin{solution}
	Caso $c_{n+1} = 0$ o valor ótimo é mantido, caso contrário este será modificado.
	\end{solution}
	\end{enumerate}
	
	\item [1.34] Considere o problema:  Minimizar $\mathbf{c}^T \mathbf{x}$ sujeito a $\mathbf{A}\mathbf{x} \geq \mathbf{b}$, $\mathbf{x} \geq 0$. Suponha que uma restrição, digamos $i$, é retirada do problema.
	\begin{enumerate}
	\item O que acontece com a região factível?
	
	\begin{solution}
	A região factível pode ou não ser modificada.
	\end{solution}
	
	\item O que acontece com o valor ótimo?
	
	\begin{solution}
	Caso a região factível não seja modificada o valor ótimo é mantido. Já se a região factível for alterada temos que o valor ótimo é modificado se a folga da $i$-ésima restrição era igual a zero ou é mantido caso contrário.
	\end{solution}
	\end{enumerate}
	
	\item [1.35] Considere o problema:  Minimizar $\mathbf{c}^T \mathbf{x}$ sujeito a $\mathbf{A}\mathbf{x} \geq \mathbf{b}$, $\mathbf{x} \geq 0$. Suponha que uma variável, digamos $x_k$, é retirada do problema.
	\begin{enumerate}
	\item O que acontece com a região factível?
	
	\begin{solution}
	A região factível diminui.
	\end{solution}
	
	\item O que acontece com o valor ótimo?
	
	\begin{solution}
	Caso $x_{k}^* = 0$ o valor ótimo é mantido, caso contrário este será modificado.
	\end{solution}
	\end{enumerate}
\end{description}